import rand


def merge(ll :list, l2: list, reverse=True) -> list:

    k = []

    while len(l1) > 0 and len(l2) > 0:

        if reverse == True:
            if l1[0] >= l2[0]:
                k.append(l1.pop(0))
            else:
                k.append(l2.pop(0))
        else:
            if l1[0] <= l2[0]:
                k.append(l1.pop(0))
            else:
                k.append(l2.pop(0))
    k += l1
    k += l2
    return k


def sort(data, reverse=True):

    if len(data) == 1:
        return data

    mid = len(data) // 2

    left = data[mid:]
    right = data[:mid]

    l1 = sort(left)
    l2 = sort(right)

    return merge(l1, l2, reverse)


if __name__ == "__main__":
    data = rand.rand(0, 100, 20)
    print(sort(data, reverse=False))
